Tugu ini diilhamkan pada tahun 1939 oleh arkitek Portugis José Ângelo Cottinelli Telmo, dan pengukir Leopoldo de Almeida, sebagai suar sementara semasa pembukaan Pameran Dunia Portugis pada Jun 1940.[1] Tugu kepada Penemuan mewakili idealisasi romantik penjelajahan Portugis yang tipikal dalam rejim Estado Novo António de Oliveira Salazar. Ia pada asalnya dibina sebagai pembinaan sementara, terletak di Praça do Império sebagai sebahagian daripada projek pembaharuan bandar yang disukai oleh menteri Duarte Pacheco, tetapi dengan penentangan Cottinelli Telmo.[1] Namun, oleh Jun 1943, struktur asal telah dirobohkan selepas eksposisi kerana tiada pemformalkan konkrit projek itu.[1][2]

Pada 3 Februari 1958, dalam dekri No. 41-517, kerajaan, melalui Ministério de Obras Publicas (Kementerian Kerja Raya), Wilayah Luar Negara dan Perbandaran Câmara Lisbon, menaikkan pangkat hasrat untuk membina Tugu Tetap Penemuan.[1] Antara November 1958 dan Januari 1960, tugu baharu itu dibina dalam simen dan batu berwarna merah jambu (dari Leiria), dan arca-arca yang diukir daripada batu kapur yang digali dari wilayah Sintra.[1] Projek baharu itu telah diperbesarkan daripada model asal 1940 sebagai sebahagian daripada peringatan untuk meraikan seratus tahun kelima kematian Infante Putera Henrique si Pelayar.[1]

Walaupun projek itu berdasarkan rancangan Cottinelli Telmo, beliau telah digantikan selepas kematiannya oleh António Pardal Monteiro (sebagai arkitek utama), dan kajian kestabilan telah disiapkan di bawah arahan jurutera Edgar Cardoso, Ruy Correia dan António Franco e Abreu.[1] Pelan dalaman telah dilaksanakan oleh António Pardal Monteiro, yang juga bekerja dengan Cristino da Silva untuk merancang dataran monumental. Bahagian utara hartanah telah disiapkan oleh firma Pardal Monteiro, manakala kawasan selatan telah disiapkan oleh José Raimundo.[1] Arca telah dimodelkan oleh Leopoldo de Almeida, dengan bantuan pengukir Soares Branco dan António Santos, menggunakan model oleh António Cândido dan Carlos Escobar (di bawah arahan António Branco dan Alfredo Henriques).[1]

Dirasmikan pada 9 Ogos 1960, ia merupakan salah satu daripada beberapa projek di seluruh negara yang bertujuan untuk menandakan Comemorações Henriquinas (perayaan menandakan ulang tahun kematian Putera Henrique si Pelayar).[1][3] Namun ia tidak selesai sepenuhnya sehingga 10 Oktober 1960, dipindahkan ke tanggungjawab Administração Geral do Porto de Lisboa (Pentadbiran Am Pelabuhan Lisbon).

Walaupun pada tahun 1962, perjanjian telah ditandatangani dengan Perbandaran Câmara Lisbon untuk memindahkan gelarannya, antara 1960 dan 1979 tiada apa yang dilakukan dengan tugu itu.[1] Satu dokumen (Despacho No.57/P/79) yang diterbitkan dalam jurnal perbandaran (No. 13260, 5 November 1979) memajukan hasrat bandar itu untuk menghasilkan pameran tetap, tetapi hanya pada tahun 1985 kerja-kerja awam menyiapkan pusat kebudayaan itu. (Bahasa Portugis: Centro Cultural das Descobertas) yang merasmikan akses awam ke bahagian atas struktur, selain mewujudkan ruang untuk dek pemerhatian, auditorium dan dewan untuk pameran.

Pada April 2003, pengurusan Padrão dos Descobrimentos telah diletakkan dalam jagaan syarikat awam Gestão de Equipamentos e Animação Cultural (EGEAC, E.E.M.).